package zx.lrn.notes.basic_grammer.about_collections;

import java.util.LinkedHashMap;
import java.util.Map;

/**
 * @ClassName: LRUcache
 * @Description: LRU缓存简易实现：LRU缓存意为最近最少使用缓存，缓存容量有限，当缓存满后，使用LRU算法， 会将现存缓存中最久没使用的字块替换掉
 *               JAVA集合框架中，LinkedHashMap的性质使它可以非常简单的实现LRU缓存
 * @Author: zhaoxuan
 * @Date: 2020/3/5 23:12
 **/
public class LRUcache {

    private static Map<String, String> cache;

    public static void main(String[] args) {
        /**
         * LinkedHashMap的数据结构由散列表和双向链表配合构成。 LinkedHashMap可以记住元素的插入顺序，元素插入后虽然还是放在哈希桶中，但是在迭代时将按照插入顺序进行;
         * 当初始化LinkedHashMap的第三个参数为true（默认false）时，LinkedHashMap内元素的顺序将按照访问顺序决定
         * 此时每次对LinkedHashMap进行访问时，受到影响的元素将被放置到链表的尾部，基于此特性，可以轻松实现LRU
         */
        cache = new LinkedHashMap<String, String>(4, 0.75F, true) {
            /**
             * removeEldestEntry的调用发生在put元素后，当removeEldestEntry返回true时，put元素前将会删除链表首部的元素，
             * 因此，当我们设定此方法在元素个数大于某个上限时就返回true即可实现LRU缓存置换
             * 
             * @param eldest
             * @return
             */
            @Override
            protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
                return this.size() > 4;
            }
        };
        // 加满缓存
        cache.put("1", "1");
        cache.put("2", "2");
        cache.put("3", "3");
        cache.put("4", "4");
        // 先后访问元素1、2，此时链表首部元素为3
        cache.get("1");
        cache.get("2");
        // 再put时，缓存已满，删除首部元素3
        cache.put("5", "5");
        // 可得最终结果为4、1、2、5
        System.out.println(cache);

    }
}
